Improving the schedulability of soft real-time open dynamic systems: The inheritor is actually a debtor

This paper presents the Clearing Fund Protocol, a three layered protocol designed to schedule soft real-time sets of precedence related tasks with shared resources. These sets are processed in an open dynamic environment. Open because new applications may enter the system at any time and dynamic because the schedulability is tested on-line as tasks request admission. Top-down, the three layers are the Clearing Fund, the Bandwidth Inheritance and two versions of the Constant Bandwidth Server algorithms. Bandwidth Inheritance applies a priority inheritance mechanism to the Constant Bandwidth Server. However, a serious drawback is its unfairness. In fact, a task executing in a server can potentially steal the bandwidth of another server without paying any penalty. The main idea of the Clearing Fund Algorithm is to keep track of processor-time debts contracted by lower priority tasks that block higher priority ones and are executed in the higher priority servers by having inherited the higher priority. The proposed algorithm reduces the undesirable effects of those priority inversions because the blocked task can finish its execution in its own server or in the server of the blocking task, whichever has the nearest deadline. If demanded, debts are paid back in that way. Inheritors are therefore debtors. Moreover, at certain instants in time, all existing debts may be waived and the servers are reset making a clear restart of the system. The Clearing Fund Protocol showed definite better performances when evaluated by simulations against Bandwidth Inheritance, the protocol it tries to improve.     

Optimal Time-Critical Scheduling via Resource Augmentation

Abstract. We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP . We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For optimization of average flow time, these are the first results of any sort, for any NP -hard version of the problem, that indicate that it might be possible to design good approximation algorithms.     

Multicast Pull Scheduling: When Fairness Is Fine

Abstract. We investigate server scheduling policies to minimize average user perceived latency in pull-based client-server systems (systems where multiple clients request data from a server) where the server answers requests on a multicast/ broadcast channel. We first show that there is no O(1) -competitive algorithm for this problem. We then give a method to convert any nonclairvoyant unicast scheduling algorithm A to nonclairvoyant multicast scheduling algorithm B . We show that if A works well, when jobs can have parallel and sequential phases, then B works well if it is given twice the resources. More formally, if A is an s -speed c -approximation unicast algorithm, then its counterpart algorithm B is a 2s -speed c -approximation multicast algorithm. It is already known [5] that Equi-partition, which devotes an equal amount of processing power to each job, is a (2 + ε) -speed O(1 + 1/ε) -approximation algorithm for unicast scheduling of such jobs. Hence, it follows that the algorithm {BEQUI}, which broadcasts all requested files at a rate proportional to the number of outstanding requests for that file, is a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. We give another algorithm BEQUI-EDF and show that BEQUI-EDF is also a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. However, BEQUI-EDF has the advantage that the maximum number of preemptions is linear in the number of requests, and the advantage that no preemptions occur if the data items have unit size.     

Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics

In this work, a review and comprehensive evaluation of heuristics and metaheuristics for the m-machine flowshop scheduling problem with the objective of minimising total tardiness is presented. Published reviews about this objective usually deal with a single machine or parallel machines and no recent methods are compared. Moreover, the existing reviews do not use the same benchmark of instances and the results are difficult to reproduce and generalise. We have implemented a total of 40 different heuristics and metaheuristics and we have analysed their performance under the same benchmark of instances in order to make a global and fair comparison. In this comparison, we study from the classical priority rules to the most recent tabu search, simulated annealing and genetic algorithms. In the evaluations we use the experimental design approach and careful statistical analyses to validate the effectiveness of the different methods tested. The results allow us to clearly identify the state-of-the-art methods.     

A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates

In this paper, we consider an identical parallel machine scheduling problem with release dates. The objective is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose some dominance properties and two lower bounds. We also present an efficient heuristic. A branch-and-bound algorithm, in which the heuristic, the lower bounds and the dominance properties are incorporated, is proposed and tested on a large set of randomly generated instances.     

Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups

In this paper, we consider the single machine weighted tardiness scheduling problem with sequence-dependent setups. We present heuristic algorithms based on the beam search technique. These algorithms include classic beam search procedures, as well as the filtered and recovering variants. Previous beam search implementations use fixed beam and filter widths. We consider the usual fixed width algorithms, and develop new versions that use variable beam and filter widths.     

An improved NEH-based heuristic for the permutation flowshop problem

NEH is an effective heuristic for solving the permutation flowshop problem with the objective of makespan. It includes two phases: generate an initial sequence and then construct a solution. The initial sequence is studied and a strategy is proposed to solve job insertion ties which may arise in the construct process. The initial sequence which is generated by combining the average processing time of jobs and their standard deviations shows better performance. The proposed strategy is based on the idea of balancing the utilization among all machines. Experiments show that using this strategy can improve the performance of NEH significantly. Based on the above ideas, a heuristic NEH-D (NEH based on Deviation) is proposed, whose time complexity is O(mn²), the same as that of NEH. Computational results on benchmarks show that the NEH-D is significantly better than the original NEH.     

Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times

We consider a single machine scheduling problem with simple linear deterioration. Job processing times are assumed to be a simple linear function of a job-dependent growth rate and the job's starting time. We seek an optimal schedule, so as to minimize the total absolute deviation of completion times (TADC). We prove several interesting properties of an optimal schedule, and introduce two efficient heuristics which are tested against a lower bound.     

Single-machine scheduling with deteriorating jobs under a series–parallel graph constraint

This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series–parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.     

Scheduling a dynamic job shop production system with sequence-dependent setups: An experimental study

This paper presents the salient aspects of a simulation-based experimental study of scheduling rules for scheduling a dynamic job shop in which the setup times are sequence dependent. A discrete event simulation model of the job shop system is developed for the purpose of experimentation. Seven scheduling rules from the literature are incorporated in the simulation model. Five new setup-oriented scheduling rules are proposed and implemented. Simulation experiments have been conducted under various experimental conditions characterized by factors such as shop load, setup time ratios and due date tightness. The results indicate that setup-oriented rules provide better performance than ordinary rules. The difference in performance between these two groups of rules increases with increase in shop load and setup time ratio. One of the proposed rules performs better for mean flow time and mean tardiness measures.